package mo.leetcode_top;

import mo.common.ListNode;

public class L147 {

    public ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        ListNode lastSortedNode = head;
        ListNode curr = head.next;

        while (curr != null) {
            if (lastSortedNode.val <= curr.val) {
                lastSortedNode = curr;
            } else {
                ListNode pre = dummyNode;
                while (pre.next.val <= curr.val) {
                    pre = pre.next;
                }
                lastSortedNode.next = curr.next;
                curr.next = pre.next;
                pre.next = curr;
            }

            curr = lastSortedNode.next;
        }

        return dummyNode.next;
    }

}
